perm filename BLOCKS[S87,JMC] blob sn#840183 filedate 1987-05-19 generic text, type C, neo UTF8
COMMENT āŠ—   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	blocks[s87,jmc]		Heuristics for the blocks world
C00010 ENDMK
CāŠ—;
blocks[s87,jmc]		Heuristics for the blocks world

	The original efforts to use the situation calculus and
general purpose theorem provers to solve planning problems led
to combinatorial explosion.  Green (1969) used it in the blocks
world, and its computational slowness led Nilsson and Fikes (1971)
to invent STRIPS, which uses logic in a more restricted way at
the cost of reducing, generality, expressive power and the ability to take
advice.  I have never been convinced by the argument that problem
solving by logical inference necessarily leads to combinatorial
explosion.  This is because I always supposed that the problem
solving reasoning system would accept heuristic advice in the form
of declarative sentences.  Indeed this is stated in (McCarthy 1960).
Although I didn't state it then, the idea was that the heuristics
would usually be domain dependent.  I suppose this idea occurred to
other people also, although I can't recall a paper making the point.

	From time to time, I have tried to formulate heuristic advice
as declarative sentences in such a way as to enable it to be used
to control a theorem prover.  I never got a result worth publishing,
so now it seems to me to be worthwhile to set out some heuristics in
English and then discuss how they might be represented formally and
used to control the theorem prover.

	The blocks world presents some good examples.

	Suppose we have some towers of blocks and the goal is to
re-arrange the blocks into another fixed configuration of towers.
This is the most straightforward problem; we could also want merely
to attain a configuration that satisfies some conditions.  We suppose
that the towers are on a table that has plenty of room for more towers,
that a block can only be move when it is clear to a place that is clear.
Axioms for such a problem are given in (McCarthy 1986).  Here are some
heuristics.

	1. Suppose the configuration is $s$.  Certain moves might as
well be made immediately.  For example, if a block can immediately be
moved to {\it final position}, this might as well be done immediately.
By final position I mean that all the blocks below where it is to be
moved are also in final position.

	2. If a block is above a block that it will be above in
final position but is not already in final position, then it might
as well be moved to the table immediately.

	3. If a block is moved but cannot be moved to final position,
then it might as well be moved to the table.

	4. The above three heuristics can be applied to the final
configuration and its predecessors just as well as to the initial configuration
and its successors.  This is because this blocks world is symmetric
in time.  Moves are reversible, so the sequence of moves leading from
the final configuration to the initial configuration is the reverse
of a sequence going the other way.

	These heuristics solve some problems without help and reduce
the complexity of the problems they don't solve.  The simplest problem
they don't solve is ((A B) (C D)) → ((C B) (A D)), but as soon as one
of the blocks has been moved to the table, the heuristics finish the
job.

	The above heuristics all have the character of saying that
a certain move might as well be made now.  By this we mean that
making the move now never even loses time.  There may be several
moves that might as well be made, and in this case any of them
may be chosen.

	5. In searching for the shortest sequence of moves, the
positions form a directed acyclic graph (dag) rather than a tree.  An
efficient search must keep track of the states that have already
been examined.  If a path of length $m$ has already been found, then it must
reject any path as soon as the number of moves made plus the number
of blocks out of final postion reaches $m$.

	Our goal is to express the above heuristics formally and suppose
that they are used by a meta-reasoner to control a base reasoner.
In this case, assume the base reasoner
is deductive, i.e. doesn't need non-monotonic reasoning, and reasons
from the initial position about complete configurations.  In other
words its steps derive sentences of the form that a certain sequence of moves
from the initial position gives a certain (intermediate) position.
We can try to subdivide our problem by solving first the epistemological
problem of the meta-reasoner, i.e. we don't say in what order the
meta-reasoner reaches its conclusions and only require that what
steps the base reasoner should do are consequences of the meta-axioms.
Actually the base and meta reasoners should be the same; it is only that
certain predicates and objects are used in meta reasoning that aren't used
in base reasoning.

might as well do an action from a set - val

derive "use only ground atoms"
STRIPS strategies